package leetcode;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class MinimumNumberBurstBalloons {

	//给定气球的范围，当   选中的x坐标与气球的[start, end]满足 start =< x <= end时，该气球会爆炸
	public int findMinArrowShots(int[][] points) {
		if(points == null || points.length <= 0 ||points[0].length <= 0){
			return 0;
		}
		List<int[]> list = Arrays.asList(points);
		
		//将所有范围按照start坐标排序,若start坐标相同，那么按照end排序
		
		//又一次错了，不记得上次是哪个题目了，应该是interval
		//应该按照end排序
		Collections.sort(list, new Comparator<int[]>() {
			@Override
			public int compare(int[] a1, int[] a2) {
				if(a1[1] == a2[1]){
					return a1[0] - a2[0];
				}
				return a1[1] - a2[1];
			}
		});
		int length = points.length;
		int res = 0;
		for(int i = 0; i < length; ){
			int end = list.get(i)[1];
			int index = i;
			while(index < length && list.get(index)[0] <= end && list.get(index)[1] >= end){
				index++;
			}
			i = index;
			res++;
		}
		return res;
	}
}
